package org.example.likou150.array;

/*
 * https://leetcode.cn/problems/gas-station/?envType=study-plan-v2&envId=top-interview-150
 * */
public class CanCompleteCircuit {
    public static void main(String[] args) {
        int[] gas = new int[]{1,2,3,4,5};
        int[] cost = new int[]{3,4,5,1,2};
        CanCompleteCircuit canCompleteCircuit = new CanCompleteCircuit();
        System.out.println(canCompleteCircuit.canCompleteCircuit(gas, cost));
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int minGas = 0;
        int currentGas=0;
        int startIndex=0;
        int length=gas.length;
        for (int i = 0; i < length; i++) {
            currentGas += gas[i]-cost[i];
            if(currentGas < minGas){
                minGas=currentGas;
                startIndex=i+1;
            }
        }
        return currentGas >= 0 ? startIndex % length : -1;
    }
















//    public int canCompleteCircuit(int[] gas, int[] cost) {
//        int length = gas.length;
//        int globalGas = 0;
//        int globalCost = 0;
//        int current = 0;
//        int minIndex = 0;
//        for (int i = 0; i < length; i++) {
//            globalGas += gas[i];
//            globalCost += cost[i];
//            current += gas[i] - cost[i];
//            if (current < 0) {
//                minIndex = i + 1;
//                current=0;
//            }
//        }
//        return globalGas < globalCost ? -1 : (minIndex > length) ? 0 : minIndex;
//    }
}
